from RandomList import GetRandomList
def shell_sort( arr):
    arr_len = len( arr)
    step =  arr_len >> 1
    while step:
        for i in range(step,  arr_len):
            # find all elems < cur_elem before j
            j = i
            while  arr[j] <  arr[j-step] and j-step >= 0:
                arr[j], arr[j-step] =  arr[j-step], arr[j]
                j -= step
        step = step >> 1
    return arr
    
if __name__ == "__main__":
    Arr = GetRandomList(100)
    Arr = shell_sort(Arr)
    print(Arr)